package com.mamingchao.basic.arraysort.insertsort;

import com.mamingchao.basic.arraysort.Sortable;

/**
 * 即Arrays.sort()方法里的，BinarySort；升级的插入排序；前部分是排的序，新的element 选择插入位置的时候，通过二分法 查找定位插入位置。
 *
 * Created by mamingchao on 2020/11/13.
 */
public class BinarySortImpl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {
        if (arr == null || arr.length <2) {
            return;
        }

        int num = 0;

        for (int i = 1; i < arr.length  ; i++) {
            int pos = binarySearchAndInsert(arr,arr[i],0,i-1);
            if (i == pos) {
                continue;
            }
            int temp = arr[i];

            for (int j = i ; j >pos; j--) {
                //if the element is smaller than the previous element, then swap
                num ++;
                arr[j] = arr[j-1];
            }
            arr[pos] = temp;
//            printArr(arr);
        }
        System.out.println("循环次数-" + num);
    }

    /**
     * arr 是已然排好序 的数组。value 值通过 二分法查找到 需要的数组索引位置 并返回
     * left 与 right 都是闭区间
     * @param arr
     * @param value
     */
    private static int binarySearchAndInsert(int[] arr, int value, int leftIndex, int rightIndex) {

        if (rightIndex <= leftIndex) {
            if (arr[leftIndex] <= value) {
                return leftIndex + 1;
            } else
                return leftIndex;
        }

        int mid = leftIndex + (rightIndex - leftIndex)/2;

        // 左侧继续寻找
        if (arr[mid] > value) {
            return binarySearchAndInsert(arr,value,leftIndex,mid - 1);
        } else if(arr[mid] < value) {
            return binarySearchAndInsert(arr,value,mid + 1,rightIndex);
        } else { //arr[mid] == value 的情况
            return mid;
        }
    }

}
